A Low Density Parity Check (LDPC) code is introduced by Gallager in 1960s, and has received rare reviews due to its an excellent decoding performance close to a theoretical limitation of Shannon for various channel types.
A parity check matrix of the LDPC code is mostly formed of ‘0’ elements. Thus, an iterative decoding based on probability can be easily implemented due to low density that the number of non-zero elements is small, compared with a code length of the LDPC code.
Recently, the LDPC code is drawing attention as a research theme of an error correction code field, and actually suggested and used as a standard in various fields, e.g., communication, broadcasting and storage media.
It is known that superior decoding performance can be obtained when the LDPC code is decoded by using a Belief Propagation (BP) algorithm such as a sum-product algorithm. However, calculation complexity is increased when reliable information is to be restored through the BP algorithm. In addition, since a code having a long code length such as the LDOC code of the DVB-S2 standard has a high decoding complexity, it is required to develop a new method that can decrease the calculation complexity of decoding.
The BP algorithm can be simply modified into an approximation method based on the BP. The approximation method is also called a min-sum approximation. The approximation method may decrease decoding complexity, but it deteriorates decoding performance.
Hereafter, a decoding method of the LDPC code will be described.
In a BP iterative decoding method is an algorithm for correcting errors by repeatedly exchanging messages between a variable node and check node of a Tanner graph and updating messages in each node. The BP iterative decoding method uses a Log-Likelihood Ratio (LLR) values not a posterior probability as the messages needed for decoding in a Binary-Input Additive White Gaussian Noise (BIAWGN) channel.
Hereafter, a general sum-product algorithm of the LDPC code using the LLR values will be described. The general sum-product algorithm is also called a standard BP.
The parity check matrix of the LDPC code is defined as H=[hnm]; a set of variable nodes connected to mth check node is defined as N(m)={n|hnm=1}; and a set of check nodes connected to nth variable node is defined as M(n)={m|hnm=1}. Also, a codeword transmitted using a Binary Phase Shift Keying (BPSK) is defined as)
w=(w1, w2, . . . , wN)
in an Additive White Gaussian Noise (AWGN) channel having an average of 1 and a dispersion of σ2=N0/2; and a reception signal is defined as
y=(y1, y2, . . . , yN).
Based on the definition and assumption, an LLR value L(yn) corresponding to a reception signal of nth variable node is expressed as the following Equation 1.
                              L          ⁡                      (                          y              n                        )                          =                              log            ⁢                                          P                ⁡                                  (                                                            w                      n                                        =                                          0                      |                                              y                        n                                                                              )                                                            P                ⁡                                  (                                                            w                      n                                        =                                          1                      |                                              y                        n                                                                              )                                                              =                                    4              ⁢                                                y                  n                                                  N                  0                                                      =                          2              ⁢                                                y                  n                                                  σ                  2                                                                                        Eq        .                                  ⁢        1            
Meanwhile, qnm(x) is defined as a probability that a variable n is x, where xε{0,1}, under the condition that M(n) check nodes except the mth check node are satisfied. Similarly, rnm(x) is defined as a probability that the mth check node is satisfied under the condition that the variable n is x, where xε{0,1}. Also, a posterior LLR value of the nth variable node for a temporary decoding is defined as
zn(i).
When the iteration number is i, where ‘i’ is integer, an LLR message
znm(i) 
transmitted from the nth variable node to the mth check node and an LLR message
εmn(i) 
transmitted from the mth check node to the nth variable node are expressed as the following Equation 2.
                                          z                          n              ⁢                                                          ⁢              m                                      (              i              )                                =                      log            ⁢                          {                                                                    q                                          n                      ⁢                                                                                          ⁢                      m                                                              (                      i                      )                                                        ⁡                                      (                    0                    )                                                                                        q                                          n                      ⁢                                                                                          ⁢                      m                                                              (                      i                      )                                                        ⁡                                      (                    1                    )                                                              }                                      ,                              ɛ            mn                          (              i              )                                =                      log            ⁢                          {                                                                    r                    mn                                          (                      i                      )                                                        ⁡                                      (                    0                    )                                                                                        r                    mn                                          (                      i                      )                                                        ⁡                                      (                    1                    )                                                              }                                                          Eq        .                                  ⁢        2            
Meanwhile, the sum-product algorithm of the BP iterative decoding method will be described.
First,
znm(0)=L(yn)
is calculated for each of the numbers n and m based on the reception signal y received through the channel.
Then, in an iterative decoding, a check node updating operation is performed based on the following Equation 3 for each m or n, where nεN(m).
                              ɛ          mn                      (            i            )                          =                  2          ⁢                                    tanh                              -                1                                      (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    n                                                              ⁢                                                          ⁢                              tanh                ⁡                                  (                                                            z                                                                        n                          ′                                                ⁢                        m                                                                    (                                                  i                          -                          1                                                )                                                              /                    2                                    )                                                      )                                              Eq        .                                  ⁢        3            
Continuously, a variable node updating operation is performed based on the following Equations 4 and 5 for each n or m, where mεM(n).
                              z                      n            ⁢                                                  ⁢            m                                (            i            )                          =                              L            ⁡                          (                              y                n                            )                                +                                    ∑                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ⁢                  \                  ⁢                                                                          ⁢                  m                                                      ⁢                          ɛ                                                m                  ′                                ⁢                n                                            (                i                )                                                                        Eq        .                                  ⁢        4                                          z                      n            ⁢                                                                      (            i            )                          =                              L            ⁡                          (                              y                n                            )                                +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          ɛ              mn                              (                i                )                                                                        Eq        .                                  ⁢        5            
In the temporary decoding step, if
zn(i) 
is larger than 0, nth symbol wn of a temporary codeword is set to 0. Otherwise, wn is set to 1. If H(w)T=0 is satisfied, the temporary decoding is suspended. If not, the above steps, i.e., the check node updating operation and the variable node updating operation, are repeatedly performed until the iteration number reaches maximum iteration number.
Meanwhile, the min-sum approximation method simplifies the check node updating operation and reduces calculation complexity of the sum-product algorithm. In the sum-product algorithm, a hyperbolic tangent function of the check node updating operation has highest calculation amount. The hyperbolic tangent function is substituted with a minimum value of messages transmitted from neighboring variable nodes, approximated, and expressed as the following Equation 6.
                              ɛ          mn                      (            i            )                          =                              (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    n                                                              ⁢                              sign                ⁡                                  (                                      z                                                                  n                        ′                                            ⁢                      m                                                              (                                              i                        -                        1                                            )                                                        )                                                      )                    ⁢                                          ×                                    min                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ⁢                  \                  ⁢                                                                          ⁢                  n                                                      ⁢                          (                                                                z                                                            n                      ′                                        ⁢                    m                                                        (                                          i                      -                      1                                        )                                                                              )                                                          Eq        .                                  ⁢        6            
Generally, it is known that error probability of decoding method based on the min-sum approximation method is larger than error probability of the sum-product algorithm. When the Equations 3 and 6 are compared,
εmn(i) 
based on the min-sum approximation method is equal to or greater than
εmn(i) 
based on the sum-product algorithm all the time.
Therefore, two methods are used to acquire check node update value similar to the value of the Equation 3 based on the Equation 6.
One is a method of updating the check node by using a normalized factor
γ
as shown in the following Equation 7.
                              ɛ          mn                      (            i            )                          =                              (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    n                                                              ⁢                              sign                ⁡                                  (                                      z                                                                  n                        ′                                            ⁢                      m                                                              (                                              i                        -                        1                                            )                                                        )                                                      )                    ×          γ          ⁢                                          ×                                    min                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ⁢                  \                  ⁢                                                                          ⁢                  n                                                      ⁢                          (                                                                z                                                            n                      ′                                        ⁢                    m                                                        (                                          i                      -                      1                                        )                                                                              )                                                          Eq        .                                  ⁢        7            
The method is called a normalized BP approximation method and it improves decoding performance by using a normalized factor smaller than 1 as shown in the Equation 7.
The other is a method called an offset BP approximation method of updating the check node by sing an offset factor β. As shown in Equation 8 below, check node updating operation is performed using the offset factor β, where β is positive value.
                              ɛ          mn                      (            i            )                          =                              (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    n                                                              ⁢                              sign                ⁡                                  (                                      z                                                                  n                        ′                                            ⁢                      m                                                              (                                              i                        -                        1                                            )                                                        )                                                      )                    ⁢                                          ×          max          ⁢                      {                                                                                min                                                                  n                        ′                                            ∈                                                                        N                          ⁡                                                      (                            m                            )                                                                          ⁢                        \                        ⁢                                                                                                  ⁢                        n                                                                              ⁢                                                                                z                                                                        n                          ′                                                ⁢                        m                                                                    (                                                  i                          -                          1                                                )                                                                                                                -                β                            ,              0                        }                                              Eq        .                                  ⁢        8            
As shown in Equations 7 and 8, in improved two approximation methods, the approximation includes determining whether an equation value is positive or negative, searching for a minimum element among the set
{zn′m(i−1)|n′εN(m)\n}
as a representative value, and correcting an effect which
zn′m(i−1) 
except the representative value affects
εmn(i).
Herein, the correction values
γ
and β are fixed values used in the part of correcting the effect which zn′m(i−1) 
except the representative value affects
εmn(i).
That is, an effect of
zn′m(i−1) 
varying at every iteration number is not considered.
Referring to FIGS. 1 and 2, in the sum-product algorithm, distribution state of
zn′m(i−1) 
for each iteration number will be described.
FIG. 1 is a graph illustrating a magnitude distribution of messages outputted from a variable node in the sum-product algorithm. The drawing shows a distribution of an absolute LLR value
|zn′m(i−1)|
corresponding to a specific reception signal for the LDPC code having a code rate of 1/2 of DVB-S2 standard and a length 64800 when a signal-to-noise ratio (Eb/N0) is 1.0 dB.
FIG. 2 is a graph illustrating another magnitude distribution of messages outputted from the variable node in the sum-product algorithm. The drawing shows a distribution of
|zn′m(i−1)|
corresponding to a specific reception signal for the LDPC code having a code rate of 8/9 of DVB-S2 standard and a length 64800 when the signal-to-noise ratio (Eb/N0) is 3.6 dB.
The distribution varies according to reception signals, but simulations showed that the above distribution is obtained.
As shown in FIGS. 1 and 2, when code rate is relatively low, the magnitude distribution of messages outputted from the variable node moves to the right side rapidly as the decoding iteration number is increased. When the code rate is high, as the decoding iteration number is increased, the magnitude distribution makes a little more.
In case of the high code rate is high, a performance similar to the BP algorithm can be acquired by using a fixed factor. At a relatively low code rate, however, the performance is deteriorated compared to the sum-product algorithm.
In case of the high code rate, the decoding performance based on the fixed factor to compensate for the effect of
zn′m(i−1) 
except the representative value affects
εmn(i) 
is similar to that of the BP algorithm. However, at a low code rate, the decoding performance based on the fixed factor is much smaller than the decoding performance of the BP algorithm.
Since the LDPC code is decoded using the fixed factor in the conventional normalized BP algorithm and the conventional offset BP algorithm, the decoding performance is deteriorated at low code rate.